//
// Description: 839. 模拟堆
// Created by Loading on 2022/7/17.
//

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 10;

// h[N]存储堆（小根堆）中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], n;

// 交换两个点，及其映射关系，a b 为堆中的下标
void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

// 下沉，当前节点比子节点大时，调整
void down(int i) {
    // 取得当前节点和其子节点中的最小值
    int min = i;
    if (i * 2 <= n && h[i * 2] < h[min]) {
        min = i * 2;
    }
    if (i * 2 + 1 <= n && h[i * 2 + 1] < h[min]) {
        min = i * 2 + 1;
    }
    if (min != i) { // 出现了交换
        heap_swap(i, min);
        down(min);
    }
}

// 上浮，当前节点比父节点小时，调整
void up(int i) {
    while (i / 2 && h[i / 2] > h[i]) {
        heap_swap(i, i / 2);
        i /= 2;
    }
}

int main() {
    int t;
    cin >> t;

    int m = 0; // 当前是第几个插入的数
    while (t--) {
        string op;
        cin >> op;
        if (op == "I") {
            int x;
            cin >> x;
            ++m;
            ++n;
            ph[m] = n;
            hp[n] = m;
            h[n] = x;
            up(n);
        } else if (op == "PM") {
            cout << h[1] << endl;
        } else if (op == "DM") {
            heap_swap(1, n);
            --n;
            down(1);
        } else if (op == "D") {
            int k;
            cin >> k;
            k = ph[k];
            // 将第 k 个插入的数交换到堆低，然后删除
            heap_swap(k, n);
            --n;
            down(k), up(k);
        } else {
            int k, x;
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }

    return 0;
}